﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Xml;

using System.Diagnostics.Contracts;

namespace SimpleIR
{
	/// <summary>
	/// Represents an edge in the call graph.
	/// </summary>
	public sealed class CallGraphEdge
	{
		/// <summary>
		/// The caller node associated with this edge.
		/// </summary>
		private readonly IRInvokeIdentity m_caller;

		/// <summary>
		/// The callee node associated with this edge.
		/// </summary>
		private readonly IRInvokeIdentity m_callee;
		
		[ContractInvariantMethod]
		private void ObjectInvariant()
		{
			Contract.Invariant(this.m_caller != null);
			Contract.Invariant(this.m_callee != null);
		}

		public CallGraphEdge(IRInvokeIdentity caller, IRInvokeIdentity callee)
		{
			Contract.Requires(caller != null);
			Contract.Requires(callee != null);

			this.m_caller = caller;
			this.m_callee = callee;
		}

		public override String ToString()
		{
			StringBuilder sb = new StringBuilder("(");
			sb.Append(this.m_caller.ToString());
			sb.Append(" -> ");
			sb.Append(this.m_callee.ToString());
			sb.Append(")");
			return sb.ToString();
		}

		public void SerializeToDGML(XmlWriter xmlw, IRProgram p)
		{
			Contract.Requires(xmlw != null);
			Contract.Requires(p != null);

			xmlw.WriteStartElement("Link");

			xmlw.WriteAttributeString("Source", this.m_caller.ToString());
			xmlw.WriteAttributeString("Target", this.m_callee.ToString());

			xmlw.WriteAttributeString("BuiltinCall", p.MethodBodyTable.GetBodyForInvokeExactSigMatch(this.m_callee).IsBuiltin.ToString());
			
			xmlw.WriteEndElement();
		}

		public void XMLExportSimple(XmlWriter xmlw)
		{
			Contract.Requires(xmlw != null);
			
			xmlw.WriteStartElement("CallEdge");

			xmlw.WriteAttributeString("Source", this.m_caller.ToString());
			xmlw.WriteAttributeString("Target", this.m_callee.ToString());

			xmlw.WriteEndElement();
		}

		/// <summary>
		/// Return the 
		/// </summary>
		public IRInvokeIdentity CallerIdentity
		{
			get
			{
				Contract.Ensures(Contract.Result<IRInvokeIdentity>() != null);

				return this.m_caller;
			}
		}

		public IRInvokeIdentity CalleeIdentity
		{
			get
			{
				Contract.Ensures(Contract.Result<IRInvokeIdentity>() != null);

				return this.m_callee;
			}
		}
	}

	/// <summary>
	/// Represents a single node in the call graph.
	/// </summary>
	public sealed class CallGraphNode
	{
		/// <summary>
		/// The invoke definition that this node is representing.
		/// </summary>
		private readonly IRInvokeIdentity m_def;

		/// <summary>
		/// The incomming call edges to this node.
		/// </summary>
		private readonly List<CallGraphEdge> m_callin;

		/// <summary>
		/// The outgoing call edges from this node.
		/// </summary>
		private readonly List<CallGraphEdge> m_callout;

		/// <summary>
		/// The set of methods that may be invoked in a call chain starting from this call node.
		/// </summary>
		private readonly HashSet<IRInvokeIdentity> m_reachablefuncs;

		/// <summary>
		/// The timestep when the analysis first encounters the node
		/// </summary>
		public int AnalysisDiscoverTime;

		/// <summary>
		/// A time counter for dfs traversals
		/// </summary>
		public int DFSFinishTime;

		internal enum DFSColor { White, Grey, Black };

		internal DFSColor VisitColor;

		/// <summary>
		/// True if this node is part of a SCC call cycle in the statically constructed call graph.
		/// </summary>
		internal bool IsInStaticCallGraphSCC;

		/// <summary>
		/// True if this node and all calls reachable from it are acyclic parts of the statically constructed call graph.
		/// </summary>
		internal bool IsInStaticCallGraphSimpleCallComponent;

		[ContractInvariantMethod]
		private void ObjectInvariant()
		{
			Contract.Invariant(this.m_def != null);
			Contract.Invariant(this.m_callin != null);
			Contract.Invariant(this.m_callout != null);
			Contract.Invariant(this.m_callin != this.m_callout);
			Contract.Invariant(this.m_reachablefuncs != null);
		}

		public CallGraphNode(IRInvokeIdentity fc)
		{
			Contract.Requires(fc != null);
			
			this.m_def = fc;
			this.m_callin = new List<CallGraphEdge>();
			this.m_callout = new List<CallGraphEdge>();
			this.m_reachablefuncs = new HashSet<IRInvokeIdentity>();

			this.AnalysisDiscoverTime = -1;
			this.DFSFinishTime = -1;
			this.VisitColor = DFSColor.White;

			this.IsInStaticCallGraphSCC = false;
			this.IsInStaticCallGraphSimpleCallComponent = true;
		}

		public override String ToString()
		{
			StringBuilder sb = new StringBuilder();
			sb.Append(this.m_def.ToString() + " => {");
			bool first = true;
			foreach(CallGraphEdge iid in this.m_callout)
			{
				if(!first)
					sb.Append(", ");
				first = false;
				sb.Append(iid.ToString());
			}
			sb.Append("}");
			return sb.ToString();
		}

		public void SerializeToDGML(XmlWriter xmlw, IRProgram p)
		{
			Contract.Requires(xmlw != null);
			Contract.Requires(p != null);

			xmlw.WriteStartElement("Node");
			xmlw.WriteAttributeString("Id", this.m_def.ToString());

			//write call name as label
			xmlw.WriteAttributeString("Label", this.m_def.ToString());
			
			//write if it is a builtin
			xmlw.WriteAttributeString("BuiltinMethod", p.MethodBodyTable.GetBodyForInvokeExactSigMatch(this.m_def).IsBuiltin.ToString());

			xmlw.WriteEndElement();
		}

		public void XMLExportSimple(XmlWriter xmlw, IRProgram p)
		{
			Contract.Requires(xmlw != null);
			Contract.Requires(p != null);

			xmlw.WriteStartElement("Method");
			xmlw.WriteAttributeString("Label", this.m_def.ToString());
			xmlw.WriteAttributeString("BuiltinMethod", p.MethodBodyTable.GetBodyForInvokeExactSigMatch(this.m_def).IsBuiltin.ToString());
			xmlw.WriteEndElement();
		}

		/// <summary>
		/// Return the identity of the method that this node represents.
		/// </summary>
		public IRInvokeIdentity Def 
		{ 
			get 
			{
				Contract.Ensures(Contract.Result<IRInvokeIdentity>() != null);

				return this.m_def; 
			} 
		}

		/// <summary>
		/// Return a list of all the incomming call edges to this node.
		/// </summary>
		public List<CallGraphEdge> CallInList
		{ get { return this.m_callin; } }

		/// <summary>
		/// Return a list of all the outgoing call edges from this node.
		/// </summary>
		public List<CallGraphEdge> CallOutList
		{ get { return this.m_callout; } }

		/// <summary>
		/// Return the set of call graph nodes that may be reachable from some series of calls from this node.
		/// </summary>
		public HashSet<IRInvokeIdentity> ReachableNodes
		{ get { return this.m_reachablefuncs; } }
	}

	/// <summary>
	/// Represnts the statically computed call graph (which we can refine as we do the analysis).
	/// </summary>
	public sealed class CallGraph
	{
		private readonly List<CallGraphNode> m_cgl;
		private readonly Dictionary<IRInvokeIdentity, CallGraphNode> m_callToNodeMap;

		public bool UpdatedGraph;
		private int m_dfstime;

		/// <summary>
		/// If an invocation is in a strongly connected component then this maps from the associated method 
		/// def to the set of methods that are in the component;
		/// </summary>
		private readonly Dictionary<IRInvokeIdentity, HashSet<IRInvokeIdentity>> m_staticsccgroups;

		[ContractInvariantMethod]
		private void ObjectInvariant()
		{
			Contract.Invariant(this.m_cgl != null);
			Contract.Invariant(this.m_callToNodeMap != null);
		}

		internal CallGraph()
		{
			this.m_cgl = new List<CallGraphNode>();
			this.m_callToNodeMap = new Dictionary<IRInvokeIdentity, CallGraphNode>();

			this.m_staticsccgroups = new Dictionary<IRInvokeIdentity, HashSet<IRInvokeIdentity>>();
		}

		/// <summary>
		/// Get all the call graph nodes in this graph.
		/// </summary>
		public List<CallGraphNode> Nodes
		{ get { return this.m_cgl; } }

		/// <summary>
		/// Get a list of all strongly connected components post heap analysis.
		/// </summary>
		public List<List<IRInvokeIdentity>> ComputeFinalSCCList()
		{
			//do dfs
			foreach(CallGraphNode cgn in this.m_cgl)
			{
				cgn.DFSFinishTime = -1;
				cgn.VisitColor = CallGraphNode.DFSColor.White;
			}
			this.m_dfstime = 0;

			foreach(CallGraphNode cgn in this.m_cgl)
				this.DoDFSVisit_Sort(cgn);

			//sort on assending finish time
			List<CallGraphNode> allcgn = new List<CallGraphNode>(this.m_cgl);
			allcgn.Sort((CallGraphNode cgn1, CallGraphNode cgn2) => cgn2.DFSFinishTime - cgn1.DFSFinishTime);

			//do dfs for scc
			foreach(CallGraphNode cgn in this.m_cgl)
			{
				cgn.DFSFinishTime = -1;
				cgn.VisitColor = CallGraphNode.DFSColor.White;
			}
			this.m_dfstime = 0;

			List<List<IRInvokeIdentity>> resscc = new List<List<IRInvokeIdentity>>();
			foreach(CallGraphNode cgn in allcgn)
			{
				List<IRInvokeIdentity> sccl = new List<IRInvokeIdentity>();
				this.DoDFSVisit_SCC(cgn, sccl);

				if(sccl.Count != 0)
					resscc.Add(sccl);
			}

			return resscc;
		}

		private void DoDFSVisit_Sort(CallGraphNode cgn)
		{
			if(cgn.VisitColor != CallGraphNode.DFSColor.White)
				return;

			cgn.VisitColor = CallGraphNode.DFSColor.Grey;

			foreach(CallGraphEdge cge in cgn.CallOutList)
			{
				CallGraphNode tgn = this.GetCallNodeForInvokeIdentity(cge.CalleeIdentity);
				this.DoDFSVisit_Sort(tgn);
			}

			cgn.VisitColor = CallGraphNode.DFSColor.Black;
			cgn.DFSFinishTime = this.m_dfstime++;
		}

		private void DoDFSVisit_SCC(CallGraphNode cgn, List<IRInvokeIdentity> scc)
		{
			if(cgn.VisitColor != CallGraphNode.DFSColor.White)
				return;

			cgn.VisitColor = CallGraphNode.DFSColor.Grey;

			foreach(CallGraphEdge cge in cgn.CallInList)
			{
				CallGraphNode tgn = this.GetCallNodeForInvokeIdentity(cge.CallerIdentity);

				if(scc != null && (tgn.VisitColor != CallGraphNode.DFSColor.Black))
				{
					if(!scc.Contains(cgn.Def))
						scc.Add(cgn.Def);
				}

				this.DoDFSVisit_SCC(tgn, scc);
			}

			cgn.VisitColor = CallGraphNode.DFSColor.Black;
			cgn.DFSFinishTime = this.m_dfstime++;
		}

		public List<CallGraphNode> GetNodeListInTopoOrder()
		{
			List<CallGraphNode> reachnodes = new List<CallGraphNode>();

			foreach(CallGraphNode cgn in this.Nodes)
			{
				if(cgn.CallInList.Count > 0 || cgn.CallOutList.Count > 0)
				{
					reachnodes.Add(cgn);
					this.DoDFSVisit(cgn);
				}
			}

			reachnodes.Sort((CallGraphNode cgn1, CallGraphNode cgn2) => cgn1.DFSFinishTime - cgn2.DFSFinishTime);
			return reachnodes;
		}

		/// <summary>
		/// Serialize the CallGraph to DGML.
		/// </summary>
		public void SerializeToDGML(XmlWriter xmlw, IRProgram p)
		{
			xmlw.WriteStartElement("DirectedGraph", "http://schemas.microsoft.com/vs/2009/dgml");

			//order only matters for stable debug output, and in this case we know the DFS times are set ok, otherwise it is ok if all of them compare to 0.
			List<CallGraphNode> cgnlist = new List<CallGraphNode>(this.m_cgl);
			cgnlist.Sort((CallGraphNode cgn1, CallGraphNode cgn2) => cgn1.DFSFinishTime - cgn2.DFSFinishTime); 

			xmlw.WriteStartElement("Nodes");
			foreach(CallGraphNode cgn in cgnlist)
			{
				if(cgn.CallInList.Count > 0 || cgn.CallOutList.Count > 0)
					cgn.SerializeToDGML(xmlw, p);
			}
			xmlw.WriteEndElement();
			
			xmlw.WriteStartElement("Links");
			foreach(CallGraphNode cgn in cgnlist)
			{
				foreach(CallGraphEdge iid in cgn.CallOutList)
					iid.SerializeToDGML(xmlw, p);
			}
			xmlw.WriteEndElement();
			
			xmlw.WriteEndElement();
		}

		/// <summary>
		/// Serialize the CallGraph to a simple xml format.
		/// </summary>
		public void XMLExportSimple(XmlWriter xmlw, IRProgram p)
		{
			xmlw.WriteStartElement("CallGraph");

			//order only matters for stable debug output, and in this case we know the DFS times are set ok, otherwise it is ok if all of them compare to 0.
			List<CallGraphNode> cgnlist = new List<CallGraphNode>(this.m_cgl);
			cgnlist.Sort((CallGraphNode cgn1, CallGraphNode cgn2) => cgn1.DFSFinishTime - cgn2.DFSFinishTime);

			xmlw.WriteStartElement("CalledMethods");
			xmlw.WriteAttributeString("Count", cgnlist.Count((CallGraphNode n) => n.CallInList.Count > 0 || n.CallOutList.Count > 0).ToString());
			foreach(CallGraphNode cgn in cgnlist)
			{
				if(cgn.CallInList.Count > 0 || cgn.CallOutList.Count > 0)
					cgn.XMLExportSimple(xmlw, p);
			}
			xmlw.WriteEndElement();

			xmlw.WriteStartElement("Links");
			foreach(CallGraphNode cgn in cgnlist)
			{
				foreach(CallGraphEdge iid in cgn.CallOutList)
					iid.XMLExportSimple(xmlw);
			}
			xmlw.WriteEndElement();

			xmlw.WriteEndElement();
		}

		/// <summary>
		/// Add a new method node to the call graph.
		/// </summary>
		public void AddCallNode(IRInvokeIdentity inv)
		{
			Contract.Requires(inv != null);

			CallGraphNode cgn = new CallGraphNode(inv);
			this.m_cgl.Add(cgn);
			this.m_callToNodeMap.Add(inv, cgn);
		}

		/// <summary>
		/// Return true if the two calls are from the same SCC in the current call graph (according to the statically resolved call graph).
		/// </summary>
		public bool AreCallsInSameSCC_StaticCallGraph(IRInvokeIdentity inv1, IRInvokeIdentity inv2)
		{
			CallGraphNode cgn1 = this.GetCallNodeForInvokeIdentity(inv1);
			CallGraphNode cgn2 = this.GetCallNodeForInvokeIdentity(inv2);
			if((!cgn1.IsInStaticCallGraphSCC) | (!cgn2.IsInStaticCallGraphSCC))
				return false;

			return this.m_staticsccgroups[inv1].Contains(inv2);
		}

		/// <summary>
		/// Return true if the call is in a SCC (according to the statically resolved call graph).
		/// </summary>
		public bool IsCallInSCC_StaticCallGraph(IRInvokeIdentity inv)
		{
			CallGraphNode cgn = this.GetCallNodeForInvokeIdentity(inv);
			return cgn.IsInStaticCallGraphSCC;
		}

		/// <summary>
		/// Return true if the calls is a simple call -- it and all calls from it are acyclic -- according to the statically resolved call graph.
		/// </summary>
		public bool IsCallFullySimple_StaticCallGraph(IRInvokeIdentity inv)
		{
			CallGraphNode cgn = this.GetCallNodeForInvokeIdentity(inv);
			return cgn.IsInStaticCallGraphSimpleCallComponent;
		}

		/// <summary>
		/// Add the given statically resolved call edge to the graph.
		/// </summary>
		internal void AddStaticResolvedCallEdgeAsNeeded(IRInvokeIdentity caller, IRInvokeIdentity callee)
		{
			Contract.Requires(caller != null);
			Contract.Requires(callee != null);

			CallGraphNode ncaller = this.m_callToNodeMap[caller];
			CallGraphNode ncallee = this.m_callToNodeMap[callee];
			if(!ncaller.CallOutList.Exists((CallGraphEdge cge) => cge.CalleeIdentity == callee))
			{
				CallGraphEdge ncge = new CallGraphEdge(caller, callee);
				ncaller.CallOutList.Add(ncge);
				ncallee.CallInList.Add(ncge);
			}
		}

		/// <summary>
		/// Clear all the reachability information from this graph.
		/// </summary>
		internal void ClearAllStaticallyResolvedReachability()
		{
			foreach(CallGraphNode cgn in this.m_cgl)
			{
				cgn.CallInList.Clear();
				cgn.CallOutList.Clear();
				cgn.ReachableNodes.Clear();
			}
		}

		/// <summary>
		/// Return the out edge that is associated with the given method and call info (or null if no such edge exists). 
		/// </summary>
		[Pure]
		public CallGraphEdge GetOutCallEdge(IRInvokeIdentity callermethod, IRInvokeIdentity calleemethod)
		{
			Contract.Requires(callermethod != null);
			Contract.Requires(calleemethod != null);
			
			CallGraphNode cgn = this.m_callToNodeMap[callermethod];
			for(int i = 0; i < cgn.CallOutList.Count; ++i)
			{
				if(cgn.CallOutList[i].CalleeIdentity == calleemethod)
					return cgn.CallOutList[i];
			}

			return null;
		}

		/// <summary>
		/// Return true if the given call edge already exists in the graph.
		/// </summary>
		public bool ResolvedCallEdgeAlreadyAdded(IRInvokeIdentity callermethod, IRInvokeIdentity calleemethod)
		{
			Contract.Requires(callermethod != null);
			Contract.Requires(calleemethod != null);
			
			CallGraphEdge tcge = this.GetOutCallEdge(callermethod, calleemethod);
			return tcge != null;
		}

		/// <summary>
		/// Add the given analysis resolved call edge to the graph.
		/// </summary>
		public CallGraphEdge AddAnalysisResolvedCallEdge(IRInvokeIdentity callermethod, IRInvokeIdentity calleemethod)
		{
			Contract.Requires(callermethod != null);
			Contract.Requires(calleemethod != null);
			Contract.Requires(this.GetOutCallEdge(callermethod, calleemethod) == null, "only if we discover a new call context");

			Contract.Ensures(Contract.Result<CallGraphEdge>() != null);

			CallGraphNode cgn = this.m_callToNodeMap[callermethod];
			int idx = cgn.CallOutList.FindIndex((CallGraphEdge cge) => cge.CalleeIdentity == calleemethod);
			if(idx != -1)
			{
				CallGraphEdge tcge = cgn.CallOutList[idx];
				return tcge;
			}
			else
			{
				CallGraphNode tgn = this.m_callToNodeMap[calleemethod];
				CallGraphEdge tcge = new CallGraphEdge(callermethod, calleemethod);

				cgn.CallOutList.Add(tcge);
				cgn.CallOutList.Sort((CallGraphEdge cge1, CallGraphEdge cge2) => IRInvokeIdentity.ComputeInvokeCompareByName(cge1.CalleeIdentity, cge2.CalleeIdentity));

				tgn.CallInList.Add(tcge);
				tgn.CallInList.Sort((CallGraphEdge cge1, CallGraphEdge cge2) => IRInvokeIdentity.ComputeInvokeCompareByName(cge1.CallerIdentity, cge2.CallerIdentity));

				Queue<CallGraphNode> incproc = new Queue<CallGraphNode>();
				incproc.Enqueue(cgn);
				this.PropReachability(incproc);

				this.UpdatedGraph = true;
				
				return tcge;
			}
		}

		/// <summary>
		/// Recompute the DFS info as needed.
		/// </summary>
		public void RecomputeDFS()
		{
			foreach(CallGraphNode cgn in this.m_cgl)
			{
				cgn.DFSFinishTime = -1;
				cgn.VisitColor = CallGraphNode.DFSColor.White;

				cgn.CallOutList.Sort((CallGraphEdge e1, CallGraphEdge e2) => this.GetCallNodeForInvokeIdentity(e1.CalleeIdentity).AnalysisDiscoverTime - this.GetCallNodeForInvokeIdentity(e2.CalleeIdentity).AnalysisDiscoverTime);
			}

			this.m_dfstime = 0;

			foreach(CallGraphNode cgn in this.m_cgl)
				this.DoDFSVisit(cgn);
		}

		private void DoDFSVisit(CallGraphNode cgn)
		{
			if(cgn.VisitColor != CallGraphNode.DFSColor.White)
				return;

			cgn.VisitColor = CallGraphNode.DFSColor.Grey;

			foreach(CallGraphEdge cge in cgn.CallOutList)
				this.DoDFSVisit(this.GetCallNodeForInvokeIdentity(cge.CalleeIdentity));
			
			cgn.VisitColor = CallGraphNode.DFSColor.Black;
			cgn.DFSFinishTime = this.m_dfstime++;
		}

		/// <summary>
		/// Given an invoke identity return the call graph node that is associated with it.
		/// </summary>
		[Pure]
		public CallGraphNode GetCallNodeForInvokeIdentity(IRInvokeIdentity invid)
		{
			Contract.Requires(invid != null);
			Contract.Ensures(Contract.Result<CallGraphNode>() != null);

			return this.m_callToNodeMap[invid]; 
		}

		/// <summary>
		/// Once we have initialized the static call graph we want to compute the nodes in the graph that are parts of recursive SCC in the 
		/// call graph and those that may depend on some unresolved function pointer calls.
		/// </summary>
		internal void ComputeRecCallInfo(IRProgram p)
		{
			Contract.Requires(p != null);

			//identify leaf methods and initialize the processing queue with them at the front
			Queue<CallGraphNode> toproc = new Queue<CallGraphNode>();
			for(int i = 0; i < this.m_cgl.Count; ++i)
			{
				CallGraphNode cgn = this.m_cgl[i];
				if(cgn.CallOutList.Count == 0)
					toproc.Enqueue(cgn);
			}

			//compute all pairs reachability
			this.PropReachability(toproc);

			foreach(CallGraphNode cgn in this.m_cgl)
			{
				IRBodyDef bdf = p.MethodBodyTable.GetBodyForInvokeExactSigMatch(cgn.Def);
				foreach(IRInvokeIdentity rcgn in cgn.ReachableNodes)
					bdf.UsedModStaticFields.UnionWith(p.MethodBodyTable.GetBodyForInvokeExactSigMatch(rcgn).UsedModStaticFields);

				cgn.IsInStaticCallGraphSCC = cgn.ReachableNodes.Contains(cgn.Def);
				if(cgn.IsInStaticCallGraphSCC)
					this.m_staticsccgroups.Add(cgn.Def, new HashSet<IRInvokeIdentity>(cgn.ReachableNodes));
			}

			foreach(CallGraphNode cgn in this.m_cgl)
			{
				foreach(IRInvokeIdentity rinv in cgn.ReachableNodes)
				{
					CallGraphNode rcgn = this.GetCallNodeForInvokeIdentity(rinv);
					cgn.IsInStaticCallGraphSimpleCallComponent &= rcgn.IsInStaticCallGraphSCC;
				}
			}

			//remove all the staticly resolved edges and reachability info
			this.ClearAllStaticallyResolvedReachability();
		}

		/// <summary>
		/// Given a list of nodes in this, propagate the reachability information through them.
		/// </summary>
		private void PropReachability(Queue<CallGraphNode> toproc)
		{
			Contract.Requires(toproc != null);

			HashSet<CallGraphNode> pending = new HashSet<CallGraphNode>(toproc);
			while(toproc.Count != 0)
			{
				CallGraphNode tn = toproc.Dequeue();
				pending.Remove(tn);

				for(int i = 0; i < tn.CallInList.Count; ++i)
				{
					CallGraphNode sn = this.m_callToNodeMap[tn.CallInList[i].CallerIdentity];
					if((!sn.ReachableNodes.Contains(tn.Def)) || (!sn.ReachableNodes.IsSupersetOf(tn.ReachableNodes)))
					{
						sn.ReachableNodes.UnionWith(tn.ReachableNodes);
						sn.ReachableNodes.Add(tn.Def);

						if(!pending.Contains(sn))
						{
							toproc.Enqueue(sn);
							pending.Add(sn);
						}
					}
				}
			}
		}
	}
}

